#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/14 11:34
# @USER    : Shengji He
# @File    : RemoveDuplicatesSortedList2.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        """
        Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only
        distinct numbers from the original list.

        Return the linked list sorted as well.

        Example 1:
            Input: 1->2->3->3->4->4->5
            Output: 1->2->5
        Example 2:
            Input: 1->1->1->2->3
            Output: 2->3

        :param head:
        :return:
        """
        ans = ListNode('#')
        ans.next = head
        pre, cur = None, ans
        while cur:
            pre = cur
            cur = cur.next
            while cur and cur.next and cur.next.val == cur.val:
                t = cur.val
                while cur and cur.val == t:
                    cur = cur.next
            pre.next = cur
        return ans.next


if __name__ == '__main__':
    S = Solution()
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(3)
    head.next.next.next.next = ListNode(4)
    head.next.next.next.next.next = ListNode(4)
    # head.next.next.next.next.next.next = ListNode(5)
    print(S.deleteDuplicates(head))
    print('done')
